Network/Internet Routing
The Internet, sometimes called simply “the Net,” is a worldwide system of computer networks in which any one computer on a network may, with proper permission, obtain information from, or send information to, any other computer on any other network on the Internet. Routing may be defined as the process of selecting paths, or routes, on a network along which to send network traffic. In computer networks, including the Internet, routing technologies direct the transit of data from a source to a destination through various intermediate devices (which may be collectively referred to as routers). A key routing technology for the Internet is the routing protocol. Currently, the routing protocol used on the Internet is Border Gateway Protocol (BGP), defined originally in Network Working Group Request for Comments (RFC) 1771 and updated in RFC 4271. RFC 4271 defines BGP as an inter-Autonomous System (AS) routing protocol. BGP-enabled systems or devices on a network exchange network reachability (routing) information with other BGP systems or devices on the network. When a BGP-enabled system establishes a BGP connection to another system on a network, the systems interchange BGP messages to update Internet routing information on the systems. The collection of routing information on a BGP system is generally referred to as a routing table. BGP may be used for routing data internally on networks and for routing data external to networks (e.g., from one network to another on the global Internet). BGP used internally on networks may be referred to as internal BGP (iBGP); external (Internet) BGP may be referred to as eBGP.
On the global Internet, connectivity between networks may be provided by transit providers. (However, networks may also establish peer connections). Transit providers may be defined as generally large networks expressly for the purpose of providing connectivity for the Internet. A transit provider network is sometimes referred to as a “backbone.” Transit providers may be, but are not necessarily, commercial enterprises that charge for routing packets via their network infrastructure. Transit providers may provide local, regional, or international/global routing on the Internet. Examples of transit providers include, but are not limited to, Verizon® and Level 3® Communications.
Generally, to use a transit provider, a network must have at least one physical connection, e.g. a fiber optic or cable connection, to at least one transit provider edge or border router, via which routing protocol information, and data packets, may be exchanged. While a network may connect to a single transit provider to establish a presence on the Internet via the transit provider, many networks, especially larger networks (e.g., carriers, content delivery networks (CDNs), and large enterprises), may establish and maintain such connections to multiple transit providers. FIG. 1A illustrates several networks 120A through 120F each physically connected to two transit providers 110A and 110B. The device(s) on a network 120 that are physically connected to transit provider border routers may generally be referred to as border routers. Networks 120 may include a range of networks from small networks, such as local networks for small businesses, schools, government entities, or other relatively small public or private enterprises, to large networks, such as networks for large businesses, schools, government entities, or other relatively large public or private enterprises. Networks 120 may also include local or regional Internet Service Providers (ISP) that provides Internet connectivity to residential customers, small entities, etc. Networks 120 may also include the networks of commercial Web enterprises or e-businesses that, for example, provide electronic retail sales or web services to customers via the Internet. A network 120 may include two or more subnetworks, data centers, smaller local networks, or other network components that are interconnected to form a larger network 120.
FIG. 1B illustrates example routes between two networks provided by two transit providers. Border routers of networks 120A and 120B are physically connected to border routers of transit providers 110A and 110B. Each transit provider 110 may provide one or more paths or routes between networks 120A and 120B via which packets may be sent. Each route passes through one or more nodes of the respective transit provider 110. A node may be a switch, router, computer system, or any other networking component. A path may pass through one or more external nodes as shown on route 110A1. An external node may, for example, be a border router of another network. Each route may include one or more “hops,” the connection between two nodes via which packets are exchanged. As shown in FIG. 1B, some routes may have fewer hops than other routes. For example, route 110A3 includes two hops (ignoring the physical connections between the border routers), while route 110B2 includes four hops. Each transit provider 110 provides routing information to each connected network 120 via routing protocol (e.g., BGP) sessions established between the border routers. This routing information includes descriptions of the routes provided by the respective transit provider 110 between the networks 120A and 120B, as well as the descriptions of routes to other networks 120.
Conventionally, the border router and transit provider router establish a routing protocol (e.g., BGP) connection over the physical connection, and the transit provider router provides the border router with routing information available through the transit provider. The border router collects and stores this routing information (and routing information from other transit providers, if any, that the border router is connected to) as a routing table. The routing table for the global Internet may be referred to as the global Internet routing table. The network border router may perform other functions on the routing information, for example assuring that there are no “loop” routes in the routing table by excluding routes that include the network's border router.
The global Internet routing table is large, currently including over 300,000 routes, and is growing steadily. Many networks, for example carriers, content delivery networks (CDNs), and large enterprise networks, may need to route their external traffic based on the entire Internet routing table. Larger networks are generally connected to two or more transit providers and peers, and must choose appropriate routes to different parts of the Internet. Most other types of routing (enterprise and much of what happens internally within data centers or networks) may require much smaller routing tables (1000s of routes); Internet-bound traffic is handed off to transit providers for routing. Generally, high speed routing (10 gb and up) is hardware accelerated: custom ASICs (Application-Specific Integrated Circuits) perform the bulk of the work, with traditional CPUs (Central Processing Units) performing control-plane functions. A key feature of these ASICs is the size of the forwarding table or Forwarding Information Base (FIB) that they support. Larger FIBs substantially increase the cost and complexity of the ASICs.
A result of the above is that the route table capacity of networking devices has become bi-modal in distribution between Internet-scale routers and commodity routers. Internet-scale routers (referred to herein as large-scale routers) may support one million or more routes. These large-scale routers are manufactured by a relatively small number of companies (e.g., Cisco® Systems, Inc. and Juniper® Networks, Inc.), tend to be expensive (e.g., $300,000-$1,000,000), and sell in relatively small volumes. In addition, these systems are generally proprietary systems that typically do not support customization or user extension. Commodity routers (referred to herein as small-scale routers) support a much smaller number of routes (e.g., 16K-32K routes), and high market volume tends to keep prices relatively low (e.g., $15,000 and under). Most networks use these small-scale routers for internal network routing (e.g., using Open Shortest Path First (OSPF)), although some very large networks may use large-scale routers for at least some internal networking.
FIG. 1C illustrates a network connected to the Internet via physical connections between transit providers and large-scale border router(s), according to the prior art. Network 120A may include multiple computing and peripheral devices 150 such as servers, workstations, printers, storage systems, etc., which may be referred to as endpoint devices, as well as multiple internal networking devices 140 such as internal (generally small-scale) routers, switches, bridges, etc. Network 120A may need to route inbound and outbound external traffic to other networks or devices on the Internet based on the entire Internet routing table 132. Conventionally, because of the large number of routes in the global Internet routing table (300,000+), network 120 will include one or more large-scale border routers 130 that are each physically connected to one or more transit provider 110 border routers, that each establish BGP sessions with connected transit providers 110, and that are each configured to store the full Internet routing table 132.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.